/*
Source : https://leetcode.com/problems/maximum-product-subarray/
Author : nflush@outlook.com
Date   : 2016-07-08
*/

/*
152. Maximum Product Subarray

    Total Accepted: 63947
    Total Submissions: 281051
    Difficulty: Medium

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Subscribe to see which companies asked this question
*/
class Solution {
    int getMax(int m[], int count){
        switch(count){
            case 0:
                return -2147483648;
            case 1:
                return m[0];
            case 2:
                return m[1] > 0?m[1]: m[0]*m[1];
            default:
            case 3:
                if (m[1] > 0){
                    if (m[2]>0){
                        return m[1]*m[2];
                    } else {
                        return m[0]*m[1]*m[2];
                    }
                } else {
                    if (m[2]>0){
                        return m[0]*m[1]*m[2];
                    } else {
                        return m[0] < m[2]? m[0]*m[1]: m[2]*m[1];
                    }
                }
        }
    }
public:
    int maxProduct(vector<int>& nums) {
        int m[3] = {1, 1, 1};
        int index = 0;
        int count = 0;
        int ret = -2147483648;
        int i = 0;
        if (nums.size() == 1) return nums[0];
        for (; i < nums.size() && nums[i] == 0; i++);
        if (i != 0) ret = 0;

        for (; i < nums.size(); i++){
            // if zero
            if (!nums[i]) {
                ret = max(max(ret, getMax(m, count)), 0);
                m[0] = m[1] = m[2] = 1;
                index = 0;
                count = 0;
                continue;
            }
            if (nums[i] > 0){
                m[index] *= nums[i];
                count = index +1;
            } else {
                if (count == 1)
                    ret = max(ret, getMax(m, count));
                switch(index){
                    case 0:
                    case 1:
                        m[index] *= nums[i];
                        count = index +1;
                        index++;
                        break;
                    case 2:
                        m[1] *= m[2];
                        m[2] = nums[i];
                        count = 3;
                        break;
                }
            }
//            printf("i:%d m[%d:%d:%d], ret:%d\n", i, m[0], m[1],m[2], ret);
        }
        ret = max(ret, getMax(m, count));
        return ret;
    }
};
